package leetcodev1.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LeetCode47 {

    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    //nums原数组
    //ans结果
    //idx 第i位填充
    //perm 中间结果
    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            //已经被使用了，直接跳过
            if (vis[i]) {
                continue;
            }

            //nums[i] == nums[i - 1] 存在重复元素
            //vis[i - 1]=false 说明前一个未使用，自己就不能使用，因此跳过
            //只有当直接前面的元素都用完后，才可以使用自己
            //目的是为了去重
            if ((i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }

            //-----开始------
            perm.add(nums[i]);//添加临时结果
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);//下一步
            //-----回溯------
            vis[i] = false;
//            perm.remove(idx);//和直接删除最后一个元素效果一致
            perm.remove(perm.size()-1);//删除临时结果
        }
    }
}
